package DP.打家劫舍.万诺;

import java.util.HashMap;
import java.util.Map;

public class 打家劫舍1 {
    int[] p;
    public int rob(int[] nums) {
        p = nums;
       return back(0);
    }
    private int back(int cI) {
        if(cI >= p.length){
            return 0;
        }

        int na = back(cI+2) + p[cI];
        int bu = back(cI+1);

        return Math.max(na,bu);
    }

    Map<Integer, Integer> cI_nabuMax_map = new HashMap<>();
    private int back_map(int cI) {
        if(cI >= p.length){ // 剪枝要 初na/bu=0 , 不如这个简
            return 0;
        }

        if(cI_nabuMax_map.containsKey(cI)){
            return cI_nabuMax_map.get(cI); // -> 去下个f
        }
        int na = back_map(cI+2) + p[cI];
        int bu = back_map(cI+1);
        cI_nabuMax_map.put(cI, Math.max(na,bu));
        return Math.max(na,bu);
    }

    /**
     * 1式子 [cI] = [cI+2] + p[cI] / [cI+1]
     * 2初始化 i<n
     * 3顺序 反向 { 注：内仍下/| }
     */
    public int rob_dp(int[] nums) {
        int[] dp = new int[p.length];
        // 反向
        for (int i = dp.length-1; i>=0; i--) {
            dp[i] = Math.max(
                    // 注意i+2超仅f=0, p[cI]当前仍加
                    ((i+2>=p.length)?0:dp[i+2]) + p[i],
                    (i+1>=p.length)?0:dp[i+1]
            );
        }
        return dp[0];
    }
}
